package com.cn.algorithm02.class24;

/***
 * @author: hels
 * @description:
 * 给定一个正数数组arr
 * 请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近返回 :
 * 最接近的情况下，较小集合的累加和
 **/
public class C01_SplitSumClosed {

    public static int right(int[] arr) {
        int sum  = 0;
        for (int j : arr) {
            sum += j;
        }
        System.out.println(sum);
        return process(arr, 0, sum >> 1);
    }
    private static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return 0;
        }

        int p1 = process(arr, index + 1, rest);
        int p2 = 0;
        if (arr[index] <= rest) {
            p2 = arr[index] + process(arr, index + 1, rest - arr[index]);
        }
        return Math.max(p1, p2);
    }

    // 动态规划
    public static int dp(int[] arr) {
        int sum  = 0;
        for (int j : arr) {
            sum += j;
        }
        int half = (sum >> 1);
        int N = arr.length;
        int[][] dp = new int[N + 1][half + 1];

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= half; rest++) {
                int p1 =  dp[index + 1][rest];
                int p2 = 0;
                if (arr[index] <= rest) {
                    p2 = arr[index] + dp[index +1][rest - arr[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][half];
    }

    public static int dp2(int[] arr) {
        int sum  = 0;
        for (int j : arr) {
            sum += j;
        }
        int half = (sum >> 1);
        int N = arr.length;
        int[][] dp = new int[N + 1][half + 1];

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = half; rest >= 0; rest--) {
                int p1 =  dp[index + 1][rest];
                int p2 = 0;
                if (arr[index] <= rest) {
                    p2 = arr[index] + dp[index +1][rest - arr[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][half];
    }


    public static void main(String[] args) {
       int[] arr = {23,23,12,2,7,4,7,29};
        System.out.println(right(arr));
        System.out.println(dp(arr));
        System.out.println(dp2(arr));

    }
}
